package 笔试.广联达笔试.正式批第三题机器人愉悦;

import java.util.Scanner;

//就不该用贪心法，应该使用动态规划，这是一个求解最优解的问题
//背包问题，自己的总电量是C，机器人每做一个动作都会消耗电量ci，带来愉悦度wi，求问在不超过C的情况下，能得到的最大的愉悦度
public class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int C=scanner.nextInt();
        double[] c=new double[n];
        int[] v=new int[n];
        for (int i = 0; i < n; i++)
        {
//            String[] split = scanner.nextLine().trim().split(" ");
//            c[i]= Double.valueOf(split[0]).intValue();
//            v[i]= Integer.valueOf(split[1]);
            double aDouble = scanner.nextDouble();
            c[i]=aDouble;
            v[i]= scanner.nextInt();
        }
        System.out.println(getBiggestHappy1(c, v, C));

    }
    //电量数组，对应愉悦度数组，总电量C
    //完全背包问题，可以进行的动作是无限的
    public static int getBiggestHappy(int[] c,int[] v,int C)
    {
        //动态规划
        int size=c.length;
        if (size==0)
            return 0;
        //建立dp数组
        int [][] dp=new int[size][C+1];
        //行数代表了可以放进背包的前i个物品
        //列数代表了背包的容量，因为数组是从0开始的，最后的索引是C-1，因此，要加上1，使j列数代表背包的容量，存在容量为C的情况
        //先填上只放第一个物品的情况
        for (int i = 0; i <= C; i++)
        {
            dp[0][i]=c[0]<=i?v[0]:0;//可以放下第一个物品就在第一行填上第一个物品价值
        }
        for (int i = 1; i < size; i++)
        {
            for (int j = c[i]; j <= C; j++)
            {
                if (j<c[i])//放不下
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-c[i]]+v[i]);
            }
        }
        return dp[size-1][C];
    }
    public static int getBiggestHappy1(double[] c,int[] v,int C)
    {
        //动态规划
        int size=c.length;
        if (size==0)
            return 0;
        //建立dp数组
        int [] dp=new int[C+1];
        //行数代表了可以放进背包的前i个物品
        //列数代表了背包的容量，因为数组是从0开始的，最后的索引是C-1，因此，要加上1，使j列数代表背包的容量，存在容量为C的情况
        //先填上只放第一个物品的情况
        for (int i = 0; i <= C; i++)
        {
            dp[i]=c[0]<=i?v[0]:0;//可以放下第一个物品就在第一行填上第一个物品价值
        }
        for (int i = 1; i < size; i++)
        {
            for (int j = Double.valueOf(c[i]).intValue(); j <= C; j++)
            {
                dp[j]=Math.max(dp[j],dp[j-Double.valueOf(c[i]).intValue()]+v[i]);
            }
        }
        return dp[C];
    }
}









//        HashMap<Double, Integer> map = new HashMap<>();
//        TreeMap<Double, Double> treeMap = new TreeMap<>();



//        while (scanner.hasNextLine()&&n>0)
//        {
//            double ci = scanner.nextDouble();
//            int wi=scanner.nextInt();
//            double rate=wi/ci;
//            if (map.containsKey(ci))
//            {
//                if (map.get(ci)>wi)//
//                {
//                    map.replace(ci,wi);
//                    treeMap.put(rate,ci);
//                }
//            }
//            else
//            {
//                map.put(ci,wi);
//                //性价比一样的情况
////                if (treeMap.containsKey(rate))
////                {
////                    if (treeMap.get)
////                }
////                treeMap.put(rate,ci);
//            }
//
//            n--;
//        }
//        //ci电量消耗，wi愉悦度，在ci加和小于等于C的情况下，使对应的wi最大
//        //暴力法，求出所有数对的组合情况，找出愉悦度最大的值
//        //贪心，在不超过电量的情况下，每次只找性价比最高的
//        int max=0;
//        int cnt=0;
//        while (C>0&&cnt<treeMap.size())
//        {
//            Map.Entry<Double, Double> entry = treeMap.pollLastEntry();//每次弹出最大性价比的数对
//            double currentci= entry.getValue();//当前电量
//            Integer currentwi = map.get(currentci);//当前愉悦度
//            if (C>=currentci)
//            {
//                C-=currentci;
//                max+=currentwi;
//            }
//          cnt++;
//        }
//        System.out.println(max);
